package com.ly.algorithm.leetcode.backtracking;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Classname Problem22
 * @Description
 *
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 *
 *  
 *
 * 示例：
 *
 * 输入：n = 3
 * 输出：[
 *        "((()))",
 *        "(()())",
 *        "(())()",
 *        "()(())",
 *        "()()()"
 *      ]
 *
 *
 * @Date 2020/12/25 17:41
 * @Author 冷心影翼
 */
public class Problem22 {

	public static void main(String[] args) {
		Solution22 solution22 = new Solution22();
		System.out.println(solution22.generateParenthesis(4));
	}

}


class Solution22 {

	List<String> res = new ArrayList<>();

	public List<String> generateParenthesis(int n) {
		backTracking(n,new StringBuilder(),0,0);
		return res;
	}

	public void backTracking(int n,StringBuilder sb,int left,int right) {
		String s = sb.toString();
		if(s.length() == n*2) {
			if(isValid(s))
				res.add(s);
			return;
		}
		if(left<=n) {
			sb.append("(");
			backTracking(n,sb,left+1,right);
			sb.delete(sb.length()-1,sb.length());
		}
		if(right<left) {
			sb.append(")");
			backTracking(n,sb,left,right+1);
			sb.delete(sb.length()-1,sb.length());
		}

	}

	public boolean isValid(String s) {
		Stack<Character> stack = new Stack<>();
		for (int i = 0; i < s.length(); i++) {
			if(s.charAt(i) == '(') {
				stack.push('(');
			}else {
				if(stack.size() == 0)
					return false;
				stack.pop();
			}
		}
		return stack.isEmpty();
	}
}